package com.leetcode.search.dfs;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/9/14 21:33
 */
public class FindSubsequences_491 {

    List<List<Integer>> res;

    public List<List<Integer>> findSubsequences(int[] nums) {
        res = new LinkedList<>();
        dfs(nums, -1, new LinkedList<>());
//        backtrack(nums, new LinkedList<>(), 0, new boolean[nums.length]);
        return res;
    }

    private void dfs(int[] nums, int idx, LinkedList<Integer> curList) {
        // 只要当前的递增序列长度大于 1，就加入到结果 res 中，然后继续搜索递增序列的下一个值。
        if (curList.size() > 1) {
            res.add(new ArrayList<>(curList));
        }

        // 在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值。
        // 借助 set 对 [idx + 1, nums.length - 1] 范围内的数去重。
        Set<Integer> set = new HashSet<>();

        // 从idx + 1开始进行遍历
        // 有6有7是在递归条件中
        // 只有6没有7，说明已经跳出了递归
        for (int i = idx + 1; i < nums.length; i++) {
            // 1. 如果 set 中已经有与 nums[i] 相同的值了，说明加上 nums[i] 后的所有可能的递增序列之前已经被搜过一遍了，因此停止继续搜索。
            if (set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            // 2. 如果 nums[i] >= nums[idx] 的话，说明出现了新的递增序列，因此继续 dfs 搜索（因为 curList 在这里是复用的，因此别忘了 remove 哦）
            if (idx == -1 || nums[i] >= nums[idx]) {
                curList.offerLast(nums[i]);
                dfs(nums, i, curList);
                curList.pollLast();
            }
        }
    }

    public void backtrack(int[] nums, LinkedList<Integer> list, int start, boolean[] visited) {
        if (list.size() > 1)
            res.add(new LinkedList<>(list));
        for (int i = start; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])
                continue;
            if (!list.isEmpty() && list.peekLast() > nums[i])
                continue;
            list.offerLast(nums[i]);
            visited[i] = true;
            backtrack(nums, list, i + 1, visited);
            visited[i] = false;
            list.pollLast();
        }
    }

}
